#include<iostream>
using namespace std;
struct TreeNode {
	int val;
	struct TreeNode* left;
	struct TreeNode* right;
	TreeNode(int x) :
		val(x), left(NULL), right(NULL) {
	}
};
bool HasSubtree_(TreeNode* pRoot1, TreeNode* pRoot2)
{
	if (pRoot1 == nullptr)
		return true;
	while (pRoot1 && pRoot2)
	{
		if (pRoot1->val == pRoot2->val)
		{
			return HasSubtree_(pRoot1->left, pRoot2->left) && HasSubtree_(pRoot1->right, pRoot2->right);
		}
		else {
			return false;
		}
	}
	return false;
}

bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) {
	if (pRoot1 == nullptr)
		return false;
	bool flag;
	if (pRoot1->val == pRoot2->val)
		flag = HasSubtree_(pRoot1, pRoot2);
	return flag || HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2);
}

int main()
{
	TreeNode* pRoot1 = new TreeNode(8);
	TreeNode* pRoot11 = new TreeNode(8);
	TreeNode* pRoot12 = new TreeNode(7);
	TreeNode* pRoot13 = new TreeNode(9);
	TreeNode* pRoot14 = new TreeNode(2);
	TreeNode* pRoot15 = new TreeNode(4);
	TreeNode* pRoot16 = new TreeNode(7);
	pRoot1->left = pRoot11;
	pRoot1->right = pRoot12;
	pRoot11->left = pRoot13;
	pRoot11->right = pRoot14;
	pRoot14->left = pRoot15;
	pRoot14->right = pRoot16;
	TreeNode* pRoot2 = new TreeNode(8);
	TreeNode* pRoot21 = new TreeNode(9);
	TreeNode* pRoot22 = new TreeNode(2);
	pRoot2->left = pRoot21;
	pRoot2->right = pRoot22;
	cout<<HasSubtree(pRoot1, pRoot2);
}